Algorisme de Shor

L'algorisme de Shor és un algorisme quàntic per descompondre en factors un nombre N en temps O ((log N)³) i espai O(log N), anomenat així per Peter Shor.

Moltes criptografies de clau pública, com ara RSA, arribarien a ser obsoletes si l'algorisme de Shor és implementat alguna vegada en un ordinador quàntic pràctic. Un missatge xifrat amb RSA pot ser desxifrat descomponent en factors la clau pública N, que és el producte de dos nombres primers. Els algorismes clàssics coneguts no poden fer-ho en temps O((logN)^k) per a cap k, de manera que arriben a ser ràpidament poc pràctics a mesura que s'augmenta N. Per contra, l'algorisme de Shor pot trencar RSA en temps polinòmic. També s'ha ampliat per atacar moltes altres criptografies de clau pública.

Com tots els algorismes de computació quàntica, l'algorisme de Shor és probabilístic: dona la resposta correcta amb alta probabilitat, i la probabilitat d'error pot ser disminuïda repetint l'algorisme.

L'algorisme de Shor va ser demostrat en 2001 per un grup d'IBM, que va descompondre 15 en els seus factors 3 i 5, utilitzant un ordinador quàntic amb 7 qubits.